class Solution {
public:
    int binary_search(vector<int> &len, int n, int val) {
        int head = 0, tail = n, mid;
        while (head < tail) {
            mid = (head + tail + 1) >> 1;
            if (len[mid] < val) head = mid;
            else tail = mid - 1;
        }
        return head;
    }
    int lengthOfLIS(vector<int>& nums) {
        vector<int> len(nums.size() + 1);
        vector<int> dp(nums.size());
        len[0] = INT32_MIN;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            dp[i] = binary_search(len, ans, nums[i]) + 1;
            len[dp[i]] = nums[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
